Rate-Distortion (R-D) optimization is a crucial technique in video encoders. However, the widely used independent R-D optimization is far from being global optimal. In order to further improve the compression performance of High Efficiency Video Coding (HEVC), a two-pass encoding algorithm combined with both R-D dependency and R-D characteristic was proposed. Firstly, the current frame was encoded with the original method in HEVC, and the number of bits consumed by the current frame and the R-D model parameters of each Coding Tree Unit (CTU) were obtained. Then, combined with time domain dependent rate distortion optimization, the optimal Lagrange multiplier and quantization parameter for each CTU were determined according to the information including current frame bit budget and R-D model parameters. Finally, the current frame was re-encoded, where each CTU had different optimization goal according to its Lagrange multiplier. Experimental results show that the proposed algorithm achieves significant rate-distortion performance improvement. Specifically, the proposed algorithm saves 3.5% and 3.8% bitrate at the same coding quality, compared with the original HEVC encoder, under the coding configurations of low-delay B and P frames.